package com.masterlu.leetcode.daily.linkedlist.simple;

import com.masterlu.leetcode.daily.linkedlist.ListNode;

import java.util.HashSet;

/**
 * 环形链表
 * https://leetcode-cn.com/problems/linked-list-cycle/
 *
 * @Author：masterlu
 * @Date：2021/4/12 9:49 上午
 */
public class S141HasCycle {

    /**
     * 利用hashset 解决实现复杂性问题
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {

        if (null == head || head.next == null) {
            return Boolean.FALSE;
        }

        HashSet<ListNode> set = new HashSet<>();
        while (null != head) {
            if (!set.add(head)) {
                return Boolean.TRUE;
            }
            head = head.next;
        }


        return Boolean.FALSE;
    }


    /**
     * 利用快慢指针
     *
     * @return
     */
    public boolean hasCycle2(ListNode head) {

        if (null == head || null == head.next) {
            return Boolean.FALSE;
        }

        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return Boolean.FALSE;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        return Boolean.TRUE; }
}
